package shenrudigui;

public class _01走楼梯 {

    /**
     * 有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶、3阶。
     * 请实现一个方法，计算小孩有多少种上楼的方式。
     * 为了防止溢出，请将结果Mod 1000000007
     * <p>
     * 给定一个正整数int n，请返回一个数，代表上楼的方式数。
     * 保证n小于等于100000。
     */
    static final int mod = 1000000007;

    public static void main(String[] args) {
        System.out.println(recursion1(10));
        System.out.println(recursion2(10));
    }

    //从后往前
    public static int recursion1(int n) {
        if (n < 0) return 0;
        if (n == 0 || n == 1) return 1;
        if (n == 2) return 2;
        return recursion1(n - 1) % mod + recursion1(n - 2) % mod + recursion1(n - 3) % mod;
    }

    //从前往后递归
    public static int recursion2(int n) {
        if (n < 0) return 0;
        if (n == 0 || n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        int x1 = 1;
        int x2 = 2;
        int x3 = 4;
        for (int i = 4; i <= n; i++) {
            int x_1 = x1;
            x1 = x2 % mod;
            x2 = x3 % mod;
            x3 = ((x1 + x2) % mod + x_1) % mod ;
        }
        return x3;
    }
}
